package junior.贪心算法;

public class 最优装载 {
    static int[] weights = {4,5,9,2,6,1};   // 集装箱的重量
    static int maxWeight = 13;

    public static void main(String[] args) {
        int total = loading(weights,maxWeight);
        show(total);
    }

    public static int loading(int[] weights,int maxWeight){
        int len = weights.length;
        int[] weightsM = new int[len];
        for (int i = 0; i < len; i++) {
            weightsM[i] = weights[i];
        }
        weightsM = quickSort(weightsM,0, weightsM.length-1);    // 快排

        int sumWight = 0;
        int total = 0;
        for (int i = 0; i < len; i++) {
            sumWight += weightsM[i];    // 最优子结构：重量较轻者先装的贪心策略
            if(sumWight < maxWeight)
                total++;
            else
                break;

        }
        return total;
    }

    public static int[] quickSort(int[] array,int start, int end){
        int pivot = array[start];
        int i = start;
        int j = end;
        while (i<j) {
            while (i<j && array[j] > pivot)
                j--;
            while (i<j && array[i] < pivot)
                i++;
            if (i<j && array[i]==array[j]) {
                i++;
            } else {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        if (i-1 > start)
            array=quickSort(array,start,i-1);
        if (j+1 < end)
            array=quickSort(array,j+1,end);
        return array;
    }
    public static void show(int total){
        System.out.println("轮船最大载重："+ maxWeight);
        System.out.println("集装箱的个数："+ weights.length);
        System.out.print("集装箱的重量：");
        for (int i = 0; i < weights.length; i++) {
            System.out.print(weights[i]+"\t");
        }
        System.out.println("\n"+"最多的集装箱个数: "+total);
    }
}
